package sortAlgorithm;

import java.util.Arrays;
import java.util.Random;

public class InsertSort {
    public static void main(String[] args) {
        long now = System.currentTimeMillis();
        Random random = new Random();
        int[] a = new int[300];
        int[] b = new int[300];
        for (int i = 0; i < a.length; i++) {
            a[i] = random.nextInt(200);
            b[i] = random.nextInt(200);
        }
        System.out.println("排序前：");
        System.out.println(Arrays.toString(a));
        System.out.println("排序后：");
        insertSort(a, a.length - 1);
        System.out.println(Arrays.toString(a));
        System.out.println("耗时：" + (System.currentTimeMillis() - now) + " ms");
        System.out.println("排序前：");
        System.out.println(Arrays.toString(b));
        System.out.println("排序后：");
        insertSort1(b);
        System.out.println(Arrays.toString(b));
        System.out.println("耗时：" + (System.currentTimeMillis() - now) + " ms");
    }

    public static void insertSort(int[] array, int end) {
        if (end == 0) {
            return;
        }
        insertSort(array, end - 1);
        int k = array[end];
        int index = end - 1;
        while (index > -1 && k < array[index]) {
            array[index + 1] = array[index];
            index--;
        }
        array[index + 1] = k;
    }

    //递推形式
    public static void insertSort1(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int k = array[i];
            int index = i - 1;
            while (index > -1 && k < array[index]) {
                array[index + 1] = array[index];
                index--;
            }
            array[index + 1] = k;
        }
    }
}
